/**
 * 分治（单边循环法）
 * 
 * @param array 待交换的数组
 * @param startIndex 起始下标
 * @param endIndex 结束下标
 * 
 * **/
function partition(array, startIndex, endIndex) {
    // 取第一个位置（也可以选择随机位置）的元素作为基准元素
    let pivot = array[startIndex];
    let mark = startIndex;

    for (var i = startIndex+1; i <= endIndex; i++) {
        if(array[i] <pivot) {
            mark++;
            const p = array[mark];
            array[mark] = array[i];
            array[i] = p;
        }
    }

    array[startIndex] = array[mark];
    array[mark] = pivot;

    return mark;
}

function quickSort(array, startIndex, endIndex) {
    // 递归结束条件：startIndex 大于或等于 endIndex 时
    if (startIndex >= endIndex) {
        return;
    }

    // 得到基准元素位置
    let pivotIndex = partition(array, startIndex, endIndex);
    // 根据基准元素，分成两部分进行递归排序
    quickSort(array, startIndex, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, endIndex);

    return array;
}

const array = [4,4,6,5,3,2,8,1];
const myQuickSort = quickSort(array, 0, array.length - 1);

console.log(myQuickSort);